// BFS代码框架：

int BFS(Node start, Node target)
{
	queue<Node> q;

	set<Node> visited;

	q.push(start);

	visited.insert(start);

	while(!q.empty())
	{
		int sz = q.size();
		for(int i = 0; i < sz; i++)
		{
			Node cur = q.front();
			q.pop();

			if(cur == target)
			{
				return step;
			}
			for(Node x : cur.adj())
			{
				if(visited.count(x) == 0)
				{
					q.push(x);
					visited.insert(x);
				}
			}
		}
	}
	// 如果走到这里，说明图中没有找到目标节点
}


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        if(root == nullptr)
            return 0;

        int depth = 1;

        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty())
        {
            int sz = q.size();

            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                
                if(cur->left == nullptr && cur->right == nullptr)
                    return depth;

                if(cur->left != nullptr)
                    q.push(cur->left);
                if(cur->right != nullptr)
                    q.push(cur->right);

                // depth++;
            }
            depth++;
        }

        return depth;
    }
};


// BFS相对于DFS最主要的区别在于：
// BFS找到的路径一定是最短的，但代价就是空间复杂度可能比DFS大很多。

// 代码框架：
int BFS(Node start, Node target)
{
	queue<Node> q;
	set<Node> visited;

	q.push(start);
	visited.insert(start);

	while(!q.empty())
	{
		int sz = q.size();
		for(int i = 0; i < sz; i++)
		{
			Node cur = q.front();
			q.pop();
			if(cur == target)
				return step;
			for(Node x : cur.adj())
			{
				if(visited.count()==0)
				{
					q.push(x);
					visited.insert(x);
				}
			}
		}
	}
	// 走到这里，说明在图中没有找到目标节点
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) 
    {
        if(root == nullptr)
            return 0;

        queue<TreeNode*> q;
        q.push(root);

        int depth = 1;

        while(!q.empty())
        {
            int sz = q.size();

            for(int i = 0; i < sz; i++)
            {
                TreeNode* cur = q.front();
                q.pop();

                if(cur->left == nullptr && cur->right == nullptr)
                    return depth;

                if(cur->left != nullptr)
                    q.push(cur->left);
                if(cur->right != nullptr)
                    q.push(cur->right);
            }

            depth++;
        }

        return depth;
    }
};


class Solution {
public:
    int openLock(vector<string>& deadends, string target) 
    {
        // 记录需要跳过的死亡密码
        unordered_set<string> deads(deadends.begin(), deadends.end());
        // 记录已经访问过的密码，防止重复遍历
        unordered_set<string> visited;
        queue<string> q;
        // 从起点开始广度优先搜索
        int step = 0;
        q.push("0000");
        visited.insert("0000");

        while(!q.empty())
        {
            int sz = q.size();

            for(int i = 0; i < sz; i++)
            {
                string cur = q.front();
                q.pop();

                // 判断是否到达终点
                if(cur == target)
                    return step;
                if(deads.count(cur))
                    continue;

                // 将一个节点的相邻为遍历节点加入队列中
                for(int j = 0; j < 4; j++)
                {
                    string up = upOne(cur, j); // 向上波动
                    if(!visited.count(up))
                    {
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = downOne(cur, j); // 向下波动
                    if(!visited.count(down))
                    {
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }
            step++;
        }

        return -1;
    }

    string upOne(string s, int j)
    {
        if(s[j] == '9')
            s[j] = '0';
        else
            s[j] += 1;

        return s;
    }

    string downOne(string s, int j)
    {
        if(s[j] == '0')
            s[j] = '9';
        else
            s[j] -= 1;

        return s;
    }

};

class Solution {
public:
    int openLock(vector<string>& deadends, string target) 
    {
        // 记录死亡字符串
        unordered_set<string> deads(deadends.begin(), deadends.end());
        // 记录已经访问过的字符串，防止重复遍历
        unordered_set<string> visited;
        queue<string> q;
        int step = 0;
        q.push("0000");
        visited.insert("0000");

        while(!q.empty())
        {
            int sz = q.size();

            for(int i = 0; i < sz; i++)
            {
                string cur = q.front();
                q.pop();

                // 判断是否走到终点
                if(cur == target)
                    return step;
                if(deads.count(cur))
                    continue;

                for(int j = 0; j < 4; j++)
                {
                    string up = upOne(cur, j);
                    if(!visited.count(up))
                    {
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = downOne(cur, j);
                    if(!visited.count(down))
                    {
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }

            step++;
        }

        return -1;
    }

    string upOne(string s, int j)
    {
        if(s[j] == '9')
            s[j] = '0';
        else
            s[j] += 1;

        return s;
    }

    string downOne(string s, int j)
    {
        if(s[j] == '0')
            s[j] = '9';
        else
            s[j] -= 1;

        return s;
    }
};



